/*
题目：前序遍历构造二叉搜索树
给定一个整数数组，它表示BST(即 二叉搜索树 )的 先序遍历 ，构造树并返回其根。

保证 对于给定的测试用例，总是有可能找到具有给定需求的二叉搜索树。

二叉搜索树 是一棵二叉树，其中每个节点， Node.left 的任何后代的值 严格小于 Node.val , Node.right 的任何后代的值 严格大于 Node.val。

二叉树的 前序遍历 首先显示节点的值，然后遍历Node.left，最后遍历Node.right。
https://leetcode.cn/problems/construct-binary-search-tree-from-preorder-traversal/
 */
public class BstFromPreorder {
    //基本思路：第一个元素为当前树的根节点，然后寻找第一个大于根节点的元素作为左子树的边界
    public TreeNode bstFromPreorder(int[] preorder) {
        //preorder[0]为根节点，比根节点小的都在左子树
        return dfs(preorder, 0, preorder.length);
    }

    //统一左闭右开
    private TreeNode dfs(int[] preorder, int start, int end) {
        if (start >= end) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[start]);
        int pivot = searchSmaller(preorder, start, end, preorder[start]);
        root.left = dfs(preorder, start + 1, pivot);
        root.right = dfs(preorder, pivot, end);
        return root;
    }

    //找到第一个比根节点大的下标
    private int searchSmaller(int[] preorder, int start, int end, int rootVal) {
        for (int i = start; i < end; i++) {
            if (preorder[i] > rootVal) { //比根节点大
                return i;
            }
        }
        return end;
    }
}